﻿#pragma once
#include <iostream>
#include <assert.h>
#include <string.h>
#include <algorithm>
#include <list>
using std::cout;
using std::cin;
using std::endl;

namespace real
{
    template <class T>
    class vector
    {
        public:
            typedef T* iterator;
            typedef const T* const_iterator;

            iterator begin()
            {
                return _start;
            }

            iterator end()
            {
                return _finish;
            }

            const_iterator begin() const
            {
                return _start;
            }

            const_iterator end() const
            {
                return _finish;
            }
            
            // vector()
            // {}

            // c++11 强制编译器生成默认构造函数
            vector() = default;

            // vector(const T& t)
            // {
            //     push_back(t);
            // }

            // vector(const vector& v)
            // {
            //     _start = new T[v.size()];
            //     memcpy(_start, v._start, v.size());
            //     _finish = _start + v.size();
            //     _end_of_storage = _finish;
            // }

            vector( const vector& v)
            {
                cout << "copy constructor" << endl;
                reserve(v.size());
                for(auto e: v)
                {
                    push_back(e);
                }
            }

            // 迭代器区间构造
            // 类模板内可以嵌套函数模板
            template <class InputIterator>
            vector(InputIterator first, InputIterator last)
            {
                while(first != last)
                {
                    push_back(*first);
                    ++first;
                }
            }

            vector(size_t n, const T& val=T())
            {
                reserve(n);
                while(n--)
                {
                    push_back(val);
                }
            }

            // 给编译器一个更好的选择, 防止传入(int, int)被当成是迭代器区间构造
            vector(int n, const T& val=T())
            {
                assert(n >= 0);
                reserve(size_t(n));
                while(n--)
                {
                    push_back(val);
                }
            }

            ~vector()
            {
                cout << "~vector" << endl;
                if(_start){
                    delete[] _start;
                    _start = _finish = _end_of_storage = nullptr;
                }
            }

            bool empty()
            {
                return _start == _finish;
            }

            void erase(iterator pos)
            {
                assert(!empty());
                while(pos!=_finish)
                {
                    *pos = *(pos+1);
                    pos ++;
                }

                --_finish;
            }

            iterator insert(iterator pos, const T& t)
            {
                assert(pos >= _start && pos <= _finish);
                // 如果执行了扩容的操作, 意味 pos 指向了野指针(迭代器失效)
                if(_end_of_storage == _finish)
                {
                    size_t len = size_t(pos - _start) ;
                    reserve(size()==0?4:size()*2);
                    pos = _start + len;
                }

                iterator end = _finish-1;
                while(pos <= end)
                {
                    *(end+1) = *end;
                    --end;
                }
                *pos = t;
                ++_finish;
                return pos;
            }

            void push_back(const T& t)
            {
                if(_end_of_storage == _finish)
                    reserve(size()==0?4:size()*2);
                *(_finish++) = t;
            }
            
            void pop_back()
            {
                assert(!empty());
                --_finish;
            }

            void reserve(size_t n)
            {
                if(n>size())
                {
                    cout << "reserve: " << n << endl;
                    // 防止写出错误的代码, 提前记录size值
                    size_t num = size();
                    iterator tmp = new T[n];
                    // 浅拷贝隐藏了一个坑, 假如T是string, 拷贝后释放再次访问就是乱码(野指针)
                    // memcpy(tmp, _start, sizeof(T)*size());
                    // delete[] _start;
                    for(size_t i=0; i<num; ++i)
                    {
                        tmp[i] = _start[i];
                    }
                    delete[] _start;

                    // 容易坑, 提前记录size值
                    _finish = tmp + num; // + size();
                    _start = tmp;
                    _end_of_storage = _start + n ;
                }
            }

            size_t size() const
            {
                return size_t(_finish - _start);
            }

            size_t capacity() const
            {
                return size_t(_end_of_storage - _start);
            }

            void swap(vector& tmp)
            {
                std::swap(_start, tmp._start);
                std::swap(_finish, tmp._finish);
                std::swap(_end_of_storage, tmp._end_of_storage);
            }

            T& operator[](size_t index)
            {
                assert(index < size());
                return *(_start+index);
            }

            vector& operator=(vector v)
            {
                swap(v);
                return *this;
            }

        private:
            iterator _start = nullptr;
            iterator _finish = nullptr;
            iterator _end_of_storage = nullptr;

    };

    template <class T>
    void print_vector(vector<T>& t)
    {
        // for(size_t i=0; i<t.size(); ++i)
        // {
        //     cout << t[i] << " ";
        // }
        // cout << endl;

        // 前面需要加typename, 否则编译器不知道这是一个类型还是一个成员变量
        typename vector<T>::iterator it = t.begin();
        // auto it = t.begin(); // 这样写也可以
        while(it != t.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;


        for(const auto& e: t)
        {
            cout << e << " ";
        }
        cout << endl;

    }

    // print container
    template <class Container>
    void print_container(const Container& c)
    {
        for(const auto& e: c)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}